SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Population protocol</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Population protocol</span></span>

</h1>

</header>

<p>A <b>population protocol</b> is a <a href="Distributed_computing" title="Distributed computing">distributed computing</a> model formed by resource-limited mobile agents which meet in a random way according to an interaction graph. Functions are computed by updating the state of agents whenever they meet based on their previous state, and the result of the computation can be read in the states of the agents once the computation has <a href="Convergence_(mathematics)" class="mw-redirect" title="Convergence (mathematics)">converged</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Model">Model</h2></div>

<p>There is a set <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle N=\{1,2,\ldots ,n\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle N=\{1,2,\ldots ,n\}}</annotation>

</semantics>

</math></span><img src="./46de4999ceee34d1bf6626160ea4528696de1af4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:17.419ex; height:2.843ex;" alt="{\displaystyle N=\{1,2,\ldots ,n\}}" loading="lazy"></span> of nodes. Each node is a finite automaton with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s}</annotation>

</semantics>

</math></span><img src="./01d131dfd7673938b947072a13a9744fe997e632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.09ex; height:1.676ex;" alt="{\displaystyle s}" loading="lazy"></span> states. An important class of population protocols are majority algorithms, where the goal is to compute the majority bit: each node starts with a belief bit in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{0,1\}}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{0,1\}}</annotation>

</semantics>

</math></span><img src="./28de5781698336d21c9c560fb1cbb3fb406923eb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.684ex; height:2.843ex;" alt="{\displaystyle \{0,1\}}" loading="lazy"></span>and the goal is to design a protocol at the end of which the belief bit of every node is the correct initial majority bit.

</p><p>The discrete time version of the model is as follows: at each point <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle t=1,2,\ldots }">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle t=1,2,\ldots }</annotation>

</semantics>

</math></span><img src="./a231189337ab37a5f82472fe9063a59e02ba0281.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.054ex; height:2.509ex;" alt="{\displaystyle t=1,2,\ldots }" loading="lazy"></span>in time, some node <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> is selected uniformly at random. Then the node is matched with another node <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math></span><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"></span>, which is chosen uniformly at random from the set of neighbors of node <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>. Afterwards, nodes <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> and <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle j}</annotation>

</semantics>

</math></span><img src="./2f461e54f5c093e92a55547b9764291390f0b5d0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}" loading="lazy"></span> exchange memory contents and update their states. Alternatively, one can consider a continuous time model where each node <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</p><p>Protocols are often designed to minimize the convergence time or the amount of memory required per node or both.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Three_State_Protocol">Three State Protocol</h2></div>

<p>For the problem of computing the majority (consensus), there is a well-known protocol that requires only three memory states per node and has been analyzed for complete interaction graphs.<sup id="cite_ref-:0_2-0" class="reference"><a href="#cite_note-:0-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> This protocol works as follows. Let each node <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span> initialize its memory state to their initial belief bit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b_{i}\in \{0,1\}.}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b_{i}\in \{0,1\}.}</annotation>

</semantics>

</math></span><img src="./227d55c2734ae457a895a95b735cf9cc9992e845.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.968ex; height:2.843ex;" alt="{\displaystyle b_{i}\in \{0,1\}.}" loading="lazy"></span> At each point in time, when two nodes communicate, they update their state according to the following table. The row labels give the initiator’s state and the column labels the responder’s state.

</p>

<caption>Interaction rules of 3-state protocol

</caption>

<th>

</th>

<th>0

</th>

<th>?

</th>

<th>1

</th></tr>

<tr>

<th>0

</th>

<td>(0,0)

</td>

<td>(0,0)

</td>

<td>(0,?)

</td></tr>

<tr>

<th>?

</th>

<td>(?,0)

</td>

<td>(?,?)

</td>

<td>(?,1)

</td></tr>

<tr>

<th>1

</th>

<td>(1,?)

</td>

<td>(1,1)

</td>

<td>(1,1)

</td></tr></tbody></table>

<p>In words, if a node with belief <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math></span><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span> gets matched with a node with belief <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math></span><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span>, then both nodes keep their belief; the update is similar if both beliefs are <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math></span><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"></span> or both are <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ?}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ?}</annotation>

</semantics>

</math></span><img src="./fca0a4a73f3211d70a538fb6ee76beb80f4bcf44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.097ex; height:2.009ex;" alt="{\displaystyle ?}" loading="lazy"></span>. However, if the initiator's belief is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math></span><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span> and the responder's belief is <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ?}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ?}</annotation>

</semantics>

</math></span><img src="./fca0a4a73f3211d70a538fb6ee76beb80f4bcf44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.097ex; height:2.009ex;" alt="{\displaystyle ?}" loading="lazy"></span>, then the respondent updates their belief to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math></span><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span>. If on the other hand the initiator has belief <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math></span><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span> and the responder has belief <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math></span><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"></span>, then the responder changes their belief to <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ?}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ?}</annotation>

</semantics>

</math></span><img src="./fca0a4a73f3211d70a538fb6ee76beb80f4bcf44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.097ex; height:2.009ex;" alt="{\displaystyle ?}" loading="lazy"></span>. Note that this protocol is one-way: every interaction changes at most the responder’s state; thus it can be implemented with one-way communication.

</p><p>Angluin, Aspnes, and Eisenstat <sup id="cite_ref-:0_2-1" class="reference"><a href="#cite_note-:0-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> showed that, from any initial configuration that does not consist of all "<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ?}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ?}</annotation>

</semantics>

</math></span><img src="./fca0a4a73f3211d70a538fb6ee76beb80f4bcf44.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.171ex; width:1.097ex; height:2.009ex;" alt="{\displaystyle ?}" loading="lazy"></span>"s, the three-state approximate majority protocol converges to either all nodes having belief <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math></span><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span> or all nodes having belief <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math></span><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"></span> within <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(n\cdot \log n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle O(n\cdot \log n)}</annotation>

</semantics>

</math></span><img src="./837218b6d28ce003c0f81f7af156da3ede782fe1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.41ex; height:2.843ex;" alt="{\displaystyle O(n\cdot \log n)}" loading="lazy"></span> interactions with high probability. Additionally, the value chosen will be the majority non-"<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ?}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ?}</annotation>

</semantics>

</p><p>The following picture shows the evolution of the three state protocol on a set of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=500}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=500}</annotation>

</semantics>

</math></span><img src="./860dfb264c52efbeed6320a41a810514bfe88b4a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.981ex; height:2.176ex;" alt="{\displaystyle n=500}" loading="lazy"></span> nodes, where one third of the nodes have initial belief bit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0}</annotation>

</semantics>

</math></span><img src="./2aae8864a3c1fec9585261791a809ddec1489950.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 0}" loading="lazy"></span>, while the remaining two thirds have initial belief bit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math></span><img src="./92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"></span>. The fraction of "<span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle ?}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle ?}</annotation>

</semantics>

</p><p><br>

</p>

<div class="mw-heading mw-heading2"><h2 id="History">History</h2></div>

<p>Population protocols were introduced by <a href="Dana_Angluin" title="Dana Angluin">Dana Angluin</a> et al.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> as one of the first <a href="Model_of_computation" title="Model of computation">models of computation</a> to be fully <a href="Decentralization" title="Decentralization">decentralized</a> and to involve agents with highly limited resources, e.g., those found in <a href="Sensor_network" class="mw-redirect" title="Sensor network">sensor networks</a>. Since then, this abstract computation model found applications in <a href="Robotics" title="Robotics">robotics</a><sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> and <a href="Chemistry" title="Chemistry">chemistry</a>.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<p><a href="Swarm_Intelligence" class="mw-redirect" title="Swarm Intelligence">Swarm Intelligence</a>

</p>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFAlistarhAspnesEisenstatGelashvili2017" class="citation journal cs1">Alistarh, Dan; Aspnes, James; Eisenstat, David; Gelashvili, Rati; Rivest, Ronald L. (2017-01-16). <a rel="nofollow" class="external text" href="https://dl.acm.org/citation.cfm?id=3039686.3039855">"Time-space trade-offs in population protocols"</a>. Soda '17. Society for Industrial and Applied Mathematics: <span class="nowrap">2560–</span>2579. <a href="ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1602.08032">1602.08032</a></span>. <a href="Bibcode_(identifier)" class="mw-redirect" title="Bibcode (identifier)">Bibcode</a>:<a rel="nofollow" class="external text" href="https://ui.adsabs.harvard.edu/abs/2016arXiv160208032A">2016arXiv160208032A</a>.</cite> <span class="cs1-visible-error citation-comment"><code class="cs1-code">{{cite journal}}</code>: </span><span class="cs1-visible-error citation-comment">Cite journal requires <code class="cs1-code">|journal=</code> (help)</span></span>

</li>

<li id="cite_note-:0-2"><span class="mw-cite-backlink">^ <a href="#cite_ref-:0_2-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-:0_2-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><cite id="CITEREFAngluinAspnesEisenstat2007" class="citation cs2">Angluin, Dana; Aspnes, James; Eisenstat, David (2007), "A Simple Population Protocol for Fast Robust Approximate Majority", <i>Distributed Computing</i>, Lecture Notes in Computer Science, vol. 4731, Springer Berlin Heidelberg, pp. <span class="nowrap">20–</span>32, <a href="CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.80.828">10.1.1.80.828</a></span>, <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F978-3-540-75142-7_5">10.1007/978-3-540-75142-7_5</a>, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9783540751410</bdi></cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFPerronVasudevanVojnovic2009" class="citation book cs1">Perron, E.; Vasudevan, D.; Vojnovic, M. (April 2009). "Using Three States for Binary Consensus on Complete Graphs". <i>IEEE Infocom 2009</i>. IEEE. pp. <span class="nowrap">2527–</span>2535. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2Finfcom.2009.5062181">10.1109/infcom.2009.5062181</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9781424435128</bdi>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:12683772">12683772</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><a href="Dana_Angluin" title="Dana Angluin">Dana Angluin</a>, James Aspnes, Zoë Diamadi, <a href="Michael_J._Fischer" title="Michael J. Fischer">Michael J. Fischer</a>, René Peralta. <i>Computation in networks of passively mobile finite-state sensors</i>. <a href="Distributed_Computing" class="mw-redirect" title="Distributed Computing">Distributed Computing</a>, 2006. <a rel="nofollow" class="external autonumber" href="https://link.springer.com/article/10.1007/s00446-005-0138-3#/page-1">[1]</a><span style="position:relative; top: -2px;"><span typeof="mw:File"><a href="Paywall" title="closed access publication – behind paywall"></a></span></span></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text">Gregory Dudek, Michael Jenkin. <i>Computational Principles of Mobile Robotics</i>, Chapter 10.</span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text">Ho-Lin Chen, David Doty, David Soloveichik. <i>Deterministic function computation with chemical reaction networks</i>. <a href="Natural_Computing" class="mw-redirect" title="Natural Computing">Natural Computing</a>, 2014. <a rel="nofollow" class="external autonumber" href="https://link.springer.com/article/10.1007/s11047-013-9393-6">[2]</a><span style="position:relative; top: -2px;"><span typeof="mw:File"><a href="Paywall" title="closed access publication – behind paywall"></a></span></span></span>

</li>

</ol></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Parallel_computing346" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Parallel_computing346" style="font-size:114%;margin:0 4em"><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">General</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Distributed_computing" title="Distributed computing">Distributed computing</a></li>

<li><a href="Parallel_computing" title="Parallel computing">Parallel computing</a></li>

<li><a href="Parallel_algorithm" title="Parallel algorithm">Parallel algorithm</a></li>

<li><a href="Massively_parallel" title="Massively parallel">Massively parallel</a></li>

<li><a href="Cloud_computing" title="Cloud computing">Cloud computing</a></li>

<li><a href="High-performance_computing" title="High-performance computing">High-performance computing</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li>

<li><a href="Manycore_processor" title="Manycore processor">Manycore processor</a></li>

<li>GPGPU software</li>

<li><a href="Computer_network" title="Computer network">Computer network</a></li>

<li><a href="Systolic_array" title="Systolic array">Systolic array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Levels</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Instruction-level_parallelism" title="Instruction-level parallelism">Instruction</a></li>

<li><a href="Task_parallelism" title="Task parallelism">Thread</a></li>

<li><a href="Memory-level_parallelism" title="Memory-level parallelism">Memory</a></li>

<li><a href="Pipeline_(computing)" title="Pipeline (computing)">Pipeline</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Multithreading_(computer_architecture)" title="Multithreading (computer architecture)">Multithreading</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Temporal_multithreading" title="Temporal multithreading">Temporal</a></li>

<li><a href="Simultaneous_multithreading" title="Simultaneous multithreading">Simultaneous</a> (SMT)</li>

<li><a href="Simultaneous_and_heterogeneous_multithreading" title="Simultaneous and heterogeneous multithreading">Simultaneous and heterogenous</a></li>

<li><a href="Speculative_multithreading" title="Speculative multithreading">Speculative</a> (SpMT)</li>

<li><a href="Preemption_(computing)" title="Preemption (computing)">Preemptive</a></li>

<li><a href="Computer_multitasking#Cooperative_multitasking" title="Computer multitasking">Cooperative</a></li>

<li><a href="Bulldozer_(microarchitecture)#Bulldozer_core" title="Bulldozer (microarchitecture)">Clustered multi-thread</a> (CMT)</li>

<li><a href="Hardware_scout" title="Hardware scout">Hardware scout</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Theory</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parallel_RAM" title="Parallel RAM">PRAM model</a></li>

<li><a href="Parallel_external_memory" title="Parallel external memory">PEM model</a></li>

<li><a href="Analysis_of_parallel_algorithms" title="Analysis of parallel algorithms">Analysis of parallel algorithms</a></li>

<li><a href="Amdahl's_law" title="Amdahl's law">Amdahl's law</a></li>

<li><a href="Gustafson's_law" title="Gustafson's law">Gustafson's law</a></li>

<li><a href="Cost_efficiency" title="Cost efficiency">Cost efficiency</a></li>

<li><a href="Karp%E2%80%93Flatt_metric" title="Karp–Flatt metric">Karp–Flatt metric</a></li>

<li><a href="Parallel_slowdown" title="Parallel slowdown">Slowdown</a></li>

<li><a href="Speedup" title="Speedup">Speedup</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Elements</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Process_(computing)" title="Process (computing)">Process</a></li>

<li><a href="Thread_(computing)" title="Thread (computing)">Thread</a></li>

<li><a href="Fiber_(computer_science)" title="Fiber (computer science)">Fiber</a></li>

<li><a href="Instruction_window" title="Instruction window">Instruction window</a></li>

<li><a href="Array_(data_structure)" title="Array (data structure)">Array</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Coordination</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Multiprocessing" title="Multiprocessing">Multiprocessing</a></li>

<li><a href="Memory_coherence" title="Memory coherence">Memory coherence</a></li>

<li><a href="Cache_coherence" title="Cache coherence">Cache coherence</a></li>

<li><a href="Cache_invalidation" title="Cache invalidation">Cache invalidation</a></li>

<li><a href="Barrier_(computer_science)" title="Barrier (computer science)">Barrier</a></li>

<li><a href="Synchronization_(computer_science)" title="Synchronization (computer science)">Synchronization</a></li>

<li><a href="Application_checkpointing" title="Application checkpointing">Application checkpointing</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_programming" title="Computer programming">Programming</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Stream_processing" title="Stream processing">Stream processing</a></li>

<li><a href="Dataflow_programming" title="Dataflow programming">Dataflow programming</a></li>

<li><a href="Parallel_programming_model" title="Parallel programming model">Models</a>

<ul><li><a href="Implicit_parallelism" title="Implicit parallelism">Implicit parallelism</a></li>

<li><a href="Explicit_parallelism" title="Explicit parallelism">Explicit parallelism</a></li>

<li><a href="Concurrency_(computer_science)" title="Concurrency (computer science)">Concurrency</a></li></ul></li>

<li><a href="Non-blocking_algorithm" title="Non-blocking algorithm">Non-blocking algorithm</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Computer_hardware" title="Computer hardware">Hardware</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Flynn's_taxonomy" title="Flynn's taxonomy">Flynn's taxonomy</a>

<ul><li><a href="Single_instruction%2C_multiple_threads" title="Single instruction, multiple threads">Array processing</a> (SIMT)</li>

<li><a href="Flynn's_taxonomy#Pipelined_processor" title="Flynn's taxonomy">Pipelined processing</a></li>

<li><a href="Flynn's_taxonomy#Associative_processor" title="Flynn's taxonomy">Associative processing</a></li></ul></li>

<li><a href="Dataflow_architecture" title="Dataflow architecture">Dataflow architecture</a></li>

<li>GPGPU hardware</li>

<li><a href="Instruction_pipelining" title="Instruction pipelining">Pipelined processor</a></li>

<li><a href="Superscalar_processor" title="Superscalar processor">Superscalar processor</a></li>

<li><a href="Vector_processor" title="Vector processor">Vector processor</a></li>

<li><a href="Multiprocessing" title="Multiprocessing">Multiprocessor</a>

<ul><li><a href="Symmetric_multiprocessing" title="Symmetric multiprocessing">symmetric</a></li>

<li><a href="Asymmetric_multiprocessing" title="Asymmetric multiprocessing">asymmetric</a></li></ul></li>

<li><a href="Semiconductor_memory" title="Semiconductor memory">Memory</a>

<ul><li><a href="Shared_memory" title="Shared memory">shared</a></li>

<li><a href="Distributed_memory" title="Distributed memory">distributed</a></li>

<li><a href="Distributed_shared_memory" title="Distributed shared memory">distributed shared</a></li>

<li><a href="Massively_parallel" title="Massively parallel">Massively parallel</a> computer</li>

<li><a href="Computer_cluster" title="Computer cluster">Computer cluster</a>

<ul><li><a href="Beowulf_cluster" title="Beowulf cluster">Beowulf cluster</a></li></ul></li>

<li><a href="Grid_computing" title="Grid computing">Grid computer</a></li>

<li><a href="Hardware_acceleration" title="Hardware acceleration">Hardware acceleration</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="API" title="API">APIs</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Ateji_PX" title="Ateji PX">Ateji PX</a></li>

<li><a href="Boost_(C%2B%2B_libraries)" title="Boost (C++ libraries)">Boost</a></li>

<li><a href="Chapel_(programming_language)" title="Chapel (programming language)">Chapel</a></li>

<li><a href="Charm%2B%2B" title="Charm++">Charm++</a></li>

<li><a href="Coarray_Fortran" title="Coarray Fortran">Coarray Fortran</a></li>

<li><a href="Dryad_(programming)" title="Dryad (programming)">Dryad</a></li>

<li><a href="Global_Arrays" title="Global Arrays">Global Arrays</a></li>

<li><a href="GPUOpen" title="GPUOpen">GPUOpen</a></li>

<li><a href="OpenMP" title="OpenMP">OpenMP</a></li>

<li><a href="OpenCL" title="OpenCL">OpenCL</a></li>

<li><a href="OpenHMPP" title="OpenHMPP">OpenHMPP</a></li>

<li><a href="OpenACC" title="OpenACC">OpenACC</a></li>

<li><a href="Parallel_Extensions" title="Parallel Extensions">Parallel Extensions</a></li>

<li><a href="Pthreads" title="Pthreads">pthreads</a></li>

<li><a href="RaftLib" title="RaftLib">RaftLib</a></li>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Problems</th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Automatic_parallelization" title="Automatic parallelization">Automatic parallelization</a></li>

<li><a href="Deadlock_(computer_science)" title="Deadlock (computer science)">Deadlock</a></li>

<li><a href="Deterministic_algorithm" title="Deterministic algorithm">Deterministic algorithm</a></li>

<li><a href="Embarrassingly_parallel" title="Embarrassingly parallel">Embarrassingly parallel</a></li>

<li><a href="Parallel_slowdown" title="Parallel slowdown">Parallel slowdown</a></li>

<li><a href="Race_condition" title="Race condition">Race condition</a></li>

<li><a href="Software_lockout" title="Software lockout">Software lockout</a></li>

<li><a href="Scalability" title="Scalability">Scalability</a></li>

<li><a href="Starvation_(computer_science)" title="Starvation (computer science)">Starvation</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div>

<ul><li><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category: Parallel computing</li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-01-11" href="https://en.wikipedia.org/wiki/?title=Population_protocol&oldid=1194891995">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>